Homework 5¶

INSERT YOUR NAME HERE

Directions: Add work to this notebook to solve the problems below.

Be careful to name the objects you create as described in the problem. Some problems may include some tests you can run to test your code.

You must do exact arithemetic unless a problem suggests otherwise!

References: Some problems are derived from problems in the book:

  • CM: Computational Mathematics with SageMath by Paul Zimmermann, Alexandre Casamayou, Nathann Cohen, Guillaume Connan, Thierry Dumont, Laurent Fousse, François Maltey, Matthias Meulien, Marc Mezzarobba, Clément Pernet, Nicolas M. Thiéry, Erik Bray, John Cremona, Marcelo Forets, Alexandru Ghitza, and Hugh Thomas. (freely available for download)

In [ ]:
# This code is used to conduct some of the provided tests:

def _pass(s):
    s = s.replace('\n','<br/>')
    from IPython.display import HTML
    display(HTML(f'<span style="color: darkgreen; ">{s}</span>'))
_pass('Results of a successful test will be printed like this.')

def _fail(s, stop=True):
    s = s.replace('\n','<br/>')
    from IPython.display import HTML
    display(HTML(f'<span style="color: red; font-weight: bold; ">{s}</span>'))
    if stop:
        raise ValueError('You failed a test')
_fail('''Results of a failed test will be printed like this.
Typically a ValueError will also be raised, causing futher execution to stop.''', stop=False)

1. Polynomial approximation of the sine function¶

This is a minor modification of Exercise 8 from the book Computational Mathematics with SageMath.

Find the polynomial $p(x)$ of degree at most 5 that minimizes the following integral: $$\int_{-\pi}^{\pi} \big(\sin~x - p(x)\big)^{2}dx.$$

Store this polynomial as a sage polynomial p5(x) in the variable x=var('x'). Your solution should be exact (as opposed to floating-point)!

Plot the graphs of sin(x) and p5(x) on the same axes. (They should appear very close.) Also plot the error function sin(x)-p5(x).

In [ ]:

Tests for your code:

In [ ]:
try:
    p5
except Exception:
    _fail('p5 is not defined!')
try:
    p5(var('x'))
except Exception:
    _fail('p5 is not callable. Did you use the notation `p5(x)=...` to define p(x)?')
_passed = True            
try:
    if not p5.is_polynomial(var('x')):
        _passed = False
except Exception as e:
    _fail(f'Testing if p5 is a polyonomial resulted in an exception: {e}')
if not _passed:
    _fail('p5 is not a polynomial in x!')
try:
    if not p5(x).degree(x)<=5:
        _passed = False
except Exception as e:
    _fail(f'Testing if p5 is a polyonomial of degree at most 5 resulted in an exception: {e}')
if not _passed:
    _fail('p5 is not a polynomial of degree at most 5!')
_pass('Good sign: The variable p5 stores a polynomial of degree at most 5!')

2. Basis of vector subspace¶

(This is a variant of Exercise 10 from Computational Mathematics with SageMath.)

1. Determine a basis of the space of solutions of the linear homogeneous system corresponding to the matrix:

$$A = \begin{pmatrix} 2 & -3 & 2 & -12 & 33 \\ 6 & 1 & 26 & -16 & 69 \\ 10 & -29 & -18 & -53 & 32 \\ 2 & 0 & 8 & -18 & 84 \end{pmatrix}$$

That is find a subspace $S \subset \mathbb Q^5$ such that $x \in S$ if and only if $Ax=0$. Store the subspace in the variable subspace.

In [ ]:

2. Determine a basis of the space $F$ generated by the columns of $A$. Store the basis as a list of vectors in the variable basis.

In [ ]:

3. Characterize $F$ by one or several equations. Since $F \subset \mathbb Q^4$, the equations can be written as $v_i \cdot x = 0$ for $i=0, \ldots, n-1$ for some integer $n \geq 0$. That is $x \in F$ if and only if $v_i \cdot x$ for all $i$. Store a list of vectors of minimal length, $[v_0, v_1, \ldots, v_{n-1}]$ in the variable eqs.

In [ ]:
In [ ]:

3. A matrix equation¶

(This is a minor modification of exercise 11 from Computational Mathematics with SageMath.)

Let us recall the factorisation lemma for linear maps. Let $E, F, G$ be $\mathbb{K}$-vector spaces of finite dimension. (Here $\mathbb{K}$ is a field, the collection of scalars for a vector space.) Let $u \in \mathcal{L}(E, F)$ and $v \in \mathcal{L}(E, G)$. (Here $\mathcal L(E, F)$ denotes the collection of all linear maps from $E$ to $F$.) Then the following assertions are equivalent:

  1. there exists $w \in \mathcal{L}(F, G)$ such that $v = w \circ u$,
  2. $\text{Ker}(u) \subset \text{Ker}(v)$.

We search all solutions to this problem in a concrete case. Let $$ A = \begin{pmatrix} -2 & 1 & 1 \\ 8 & 1 & -5 \\ 4 & 3 & -3 \end{pmatrix}, \quad C = \begin{pmatrix} 1 & 2 & -1 \\ 2 & -1 & -1 \\ -5 & 0 & 3 \end{pmatrix}. $$

Determine all solutions $B \in \mathcal{M}_3(\mathbb{Q})$ of the equation $A = BC$. (Here $\mathcal M_3(\mathbb Q)$ denotes the collection of all $3 \times 3$ matrices with coefficients in $\mathbb Q$.)

The solution set has the form $$B_0 + S = \{B_0 + B_h:~B_h \in S\}.$$ where $B_0 \in \mathcal M_3(\mathbb Q)$ is a single solution to $A=BC$, and $S \subset M_3(\mathbb Q)$ is a subspace. Store a single solution in the variable B_0. Store a basis for $S$ as a list of rational matrices in the variable B_homogeneous_basis. That is, we should have $$S = \{c_1 B_1 + c_2 B_2+ \ldots+ c_n B_n:~c_1, \ldots, c_n \in \mathbb Q\}.$$ where $B_1, \ldots, B_n$ are the matrices in B_homogeneous_basis. In particular, all solutions to $A=BC$ should be of the form $$B = B_0 + c_1 B_1 + c_2 B_2+ \ldots+ c_n B_n,$$ where $c_1, \ldots, c_n \in \mathbb Q$.

In [ ]:

Tests for your code:

In [ ]:
_M = MatrixSpace(QQ, 3)
try:
    if not B_0 in _M:
        _fail('B_0 is not a rational 3x3 matrix. (Make sure B_0.parent() is a matrix space defined over the rationals.)')
except Exception as e:
    _fail(f'Attempting to check if B_0 is rational 3x3 matrix resulted in an error: {e}')
_pass('Your matrix B_0 lives in the right space.')
_pass('Note that I did not check that A = B_0 * C. I leave that to you!')
In [ ]:
from collections.abc import Sequence
try:
    B_homogeneous_basis
except Exception:
    _fail('`B_homogeneous_basis` is not defined.')
if not isinstance(B_homogeneous_basis, Sequence):
    _fail('`B_homogeneous_basis` is not a list.')
for i,_B in enumerate(B_homogeneous_basis):
    if not _B in _M:
        _fail(f'B_homogeneous_basis[{i}] is not a rational 3x3 matrix. (Make sure its parent is a matrix space defined over the rationals.)')
_pass('The matrices in B_homogeneous_basis live in the right space.')
_pass('It should be true that A = (B_0+B_i)*C for each B_i in B_homogeneous_basis. I leave that to you!')

4. Line integrals over line segments¶

Given a function $f(x,y)$ and two points in the plane $p_0 = (x_0, y_0)$ and $p_1 = (x_1, y_1)$, we can compute the line integral $$\int_L f~ds$$ over the line segment $L = \overline{p_0 p_1}$ with respect to arc length.

Write a function int_over_segment(f, p0, p1) which takes as input a sage function f(x,y) and two points p0 and p1 in the plane and returns the value of the line integral. Exact arithmetic should be used (though this limits the things you can integrate).

In [ ]:

Tests for your code:

In [ ]:
f(x,y) = 1
p0 = (1, 0)
p1 = (13, 5)
if int_over_segment(f, p0, p1) == 13:
    _pass('The integral is correct in this case.')
else:
    _fail('The integral computation is incorrect!')
In [ ]:
f(x,y) = sin(x) + y
p0 = (0, 0)
p1 = (pi, 0)
if int_over_segment(f, p0, p1) == 2:
    _pass('The integral is correct in this case.')
else:
    _fail('The integral computation is incorrect!')
In [ ]:
f(x,y) = x^2*y
p0 = (0, 0)
p1 = (3, 5)
if int_over_segment(f, p0, p1) == 45/4*sqrt(34):
    _pass('The integral is correct in this case.')
else:
    _fail('The integral computation is incorrect!')

5. Polynomial Basis¶

Write a function polynomial_basis_2d(degree) which takes as input an non-negative integer degree and produces the standard basis for the collection of all polynomials of degree at most degree in the variables x = var('x') and y = var('y').

We remark that the standard basis consists of terms of the form $x^a y^b$ with $a$ and $b$ non-negative integers such that $0 \leq a+b \leq d$ where $d$ is the degree. This follows the convention that $x^0$ and $y^0$ are the constant functions $1$.

The basis elements returned should lie in the polynomial ring PR = QQ[x,y]. You can convert an expression in x and y into the polynomial ring with the command PR(x+x*y^2). Below we define PR:

In [1]:
# Construct the polynomial ring
var('x y')
PR = QQ[x,y]
In [ ]:

Tests for your code:

In [ ]:
for degree in range(5):
    b = polynomial_basis_2d(degree)
    if len(b) != (degree+1)*(degree+2)/2:
        _fail(f'The wrong number of basis elements was returned for `polynomial_basis_2d({i})`.')
_pass('The correct number of basis elements was returned for degrees 0 through 4.')
In [ ]:
_PR = QQ[x,y]
for degree in range(5):
    for _p in polynomial_basis_2d(degree):
        if not _p.parent() == _PR:
            _fail('An element is not in the polynomial ring. Did you use `PR(expression)` to put it there?')
_pass('The polynomials seem to be in the polynomial ring PR. Great!')
In [ ]:
_PR = QQ[x,y]
if polynomial_basis_2d(0) != [_PR(1)]:
   _fail('The basis in degree 0 is incorrect.')
if set(polynomial_basis_2d(1)) != {_PR(1), _PR(x), _PR(y)}:
   _fail('The basis in degree 1 is incorrect.')
if set(polynomial_basis_2d(2)) != {_PR(1), _PR(x), _PR(y), _PR(x^2), _PR(x*y), _PR(y^2)}:
   _fail('The basis in degree 2 is incorrect.')
_pass('The basis was correct in degrees 0, 1, and 2.')